package array;

/**
 * @program: leecode
 * @description: 1013. 将数组分成和相等的三个部分
 * @author: gh
 * @create: 2020/03/11
 */
public class lee1013 {
    /**
     * 时间复杂度：O(N)O(N)，其中 NN 是数组 A 的长度。我们最多只需要遍历一遍数组就可以得到答案。
     * 空间复杂度：O(1)O(1)。我们只需要使用额外的索引变量 i，j 以及一些存储数组信息的变量。
     * @param A
     * @return
     */
    public static boolean canThreePartsEqualSum1(int[] A) {

        System.out.println("start");
        int sum1 = 0, sum2 = 0, sum3 = 0;

        for (int b = 1; b < A.length; b++) {
            sum3 += A[b];
        }

        for (int i = 0; i < A.length; i++) {
            sum1 += A[i];
            sum2 = 0;

            for (int a = i + 1; a < A.length; a++) {
                sum2 += A[a];
                sum3 = 0;
                for (int b = a + 1; b < A.length; b++) {
                    sum3 += A[b];
                    if (b == A.length - 1 && sum1 == sum2 && sum2 == sum3) {
                        return true;
                    }
                }

            }
        }
        return false;
    }

    public static boolean canThreePartsEqualSum2(int[] A) {


        int sum1 = 0, sum2 = 0, sum3 = 0;

        for (int b = 0; b < A.length; b++) {
            sum3 += A[b];
        }

        if (sum3 % 3 != 0) {
            return false;
        }

        int target = sum3 / 3;
        int i;
        for (i = 0; i < A.length; i++) {
            sum1 += A[i];
            if (sum1 == target) {
                break;
            }
        }

        if (sum1 != target) {
            return false;
        }

        for (int j = i + 1; j < A.length - 1; j++) {
            sum2 += A[j];
            if (sum2 == target) {
                return true;
            }
        }
        return false;
    }

    /**
     * flag
     * @param
     * @return
     * @description: 复杂度分析
     */
    public boolean canThreePartsEqualSum3(int[] A) {


        int sum = 0;
        for (int i : A) {
            sum += i;
        }
        if (sum % 3 != 0) {
            // 总和不是3的倍数，直接返回false
            return false;
        }
        int s = 0;
        int flag = 0;
        for (int i : A) {
            s += i;
            if (s == sum / 3) {
                flag++;
                s = 0;
            }
        }
        // flag不一定等于3，例如[1,-1,1,-1,1,-1,1,-1]
        return flag >= 3;


    }

    public static void main(String[] args) {
        System.out.println("test");
        int[] A = {0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1};
        boolean bool = canThreePartsEqualSum1(A);
        System.out.println(bool);
        boolean bool2 = canThreePartsEqualSum2(A);
        System.out.println(bool2);
        //error
        int[] A2 = {1, -1, 1, -1};
        boolean bool3 = canThreePartsEqualSum2(A);
        System.out.println(bool3);
    }


}
